package 第四周;

/*
 * @author  YxinMiracle
 * @date  2022-04-28 20:59
 * @Gitee: https://gitee.com/yxinmiracle
 */

import javafx.util.Pair;

import java.util.LinkedList;
import java.util.Queue;

public class 岛屿数量 {
    int m, n; // 存储图的长和宽
    public boolean[][] visited;
    public char[][] grid;

    // 使用广度优先遍历进行解题
    public int numIslands(char[][] grid) {
        int ans = 0; // 用作存储答案

        this.grid = grid;
        this.m = grid.length;
        this.n = grid[0].length;

        visited = new boolean[m][n];
        //for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) visited[i][j] = false; // 初始化访问数组

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 开始行走
                if (!visited[i][j] && grid[i][j] == '1') {
                    bfs(i, j); // 从这个点开始走
                    ans++;
                }
            }
        }
        return ans;
    }

    private void bfs(int i, int j) {
        Queue<Pair<Integer, Integer>> queue = new LinkedList<>();
        // 定义方向数组 上左下右
        int[] dx = new int[]{-1, 0, 1, 0};
        int[] dy = new int[]{0, -1, 0, 1};
        queue.add(new Pair<>(i, j));
        visited[i][j] = true;
        while (!queue.isEmpty()) {
            // 如果队列不等于空
            Pair<Integer, Integer> poll = queue.poll();
            for (int k = 0; k < 4; k++) { // 走四个方向
                int nx = poll.getKey() + dx[k];
                int ny = poll.getValue() + dy[k];
                if (nx < 0 || nx > m - 1 || ny < 0 || ny > n - 1) continue; // 越界了不进行添加数据
                if (visited[nx][ny]) continue; // 已经走过了，那么就不进行判断
                if (grid[nx][ny] != '1') continue;
                queue.add(new Pair<>(nx,ny));
                visited[nx][ny] = true; // 将队列中的点标记为已经走过的点
            }
        }
    }

}
